package com.gitee.wsl.transform.encode.pinyin.trie

import com.gitee.wsl.collections.list.LinkedList
import com.gitee.wsl.ext.base.isAlphabetic
import com.gitee.wsl.ext.base.isAscii
import com.gitee.wsl.transform.encode.pinyin.interval.IntervalTree
import com.gitee.wsl.transform.encode.pinyin.trie.handler.DefaultPayloadEmitHandler
import com.gitee.wsl.transform.encode.pinyin.trie.handler.PayloadEmitHandler
import com.gitee.wsl.transform.encode.pinyin.trie.handler.StatefulPayloadEmitHandler


/**
 * A trie implementation that carries a payload. See [Trie] for
 * details on usage.
 *
 *
 *
 * The payload trie adds the possibility to specify emitted payloads for each
 * added keyword.
 *
 *
 * @author Daniel Beck
 * @param <T> The type of the supplied of the payload.
</T> */
open class PayloadTrie<T> protected constructor(private val trieConfig: TrieConfig) {

    private val rootState: PayloadState<T> = PayloadState<T>()

    /**
     * Used by the builder to add a text search keyword with an emit payload.
     *
     * @param keyword The search term to add to the list of search terms.
     * @param emit    the payload to emit for this search term.
     * @throws NullPointerException if the keyword is null.
     */
    private fun addKeyword(keyword: String, emit: T?) {
        if (keyword.isEmpty()) {
            return
        }
        addState(keyword).addEmit(Payload(keyword, emit))
    }

    /**
     * Used by the builder to add a text search keyword.
     *
     * @param keyword The search term to add to the list of search terms.
     * @throws NullPointerException if the keyword is null.
     */
    private fun addKeyword(keyword: String) {
        if (keyword.isEmpty()) {
            return
        }
        addState(keyword).addEmit(Payload(keyword, null))
    }

    private fun addState(keyword: String): PayloadState<T> {
        var state= getRootState()
        for (character in keyword.toCharArray()) {
            val adjustedChar: Char = if (this.isCaseInsensitive) character.lowercaseChar() else character
            state = state.addState(adjustedChar)
        }
        return state
    }

    /**
     * Tokenizes the specified text and returns the emitted outputs.
     *
     * @param text The text to tokenize.
     * @return the emitted outputs
     */
    fun tokenize(text: String): Collection<PayloadToken<T>> {
        val tokens= LinkedList<PayloadToken<T>>()
        val collectedEmits: Collection<PayloadEmit<T>> = parseText(text)
        var lastCollectedPosition = -1

        for (emit in collectedEmits) {
            if (emit.start - lastCollectedPosition > 1) {
                tokens.add(createFragment(emit, text, lastCollectedPosition))
            }

            tokens.add(createMatch(emit, text))
            lastCollectedPosition = emit.end
        }

        if (text.length - lastCollectedPosition > 1) {
            tokens.add(createFragment(null, text, lastCollectedPosition))
        }

        return tokens
    }

    private fun createFragment(emit: PayloadEmit<T>?, text: String, lastCollectedPosition: Int): PayloadToken<T> {
        val text = text.substring(
            lastCollectedPosition + 1,
            emit?.start ?: text.length
        )
        return PayloadFragmentToken(text)
    }

    private fun createMatch(emit: PayloadEmit<T>, text: String): PayloadToken<T> {
        return PayloadMatchToken(
            text.substring(
                emit.start,
                emit.end + 1
            ),
            emit
        )
    }

    /**
     * Tokenizes a specified text and returns the emitted outputs.
     *
     * @param text The character sequence to tokenize.
     * @return A collection of emits.
     */
    fun parseText(text: CharSequence): Collection<PayloadEmit<T>> {
        return parseText(text, DefaultPayloadEmitHandler())
    }

    /**
     * Tokenizes the specified text by using a custom EmitHandler and returns the
     * emitted outputs.
     *
     * @param text        The character sequence to tokenize.
     * @param emitHandler The handler that will be used to parse the text.
     * @return A collection of emits.
     */
    fun parseText(text: CharSequence, emitHandler: StatefulPayloadEmitHandler<T>): Collection<PayloadEmit<T>> {
        parseText(text, emitHandler)

//        val collectedEmits = emitHandler.emits
//
//        if (!trieConfig.isAllowOverlaps) {
//            val intervalTree = IntervalTree(collectedEmits)
//            intervalTree.removeOverlaps(collectedEmits)
//        }

        var collectedEmits = emitHandler.emits

        if (!trieConfig.isAllowOverlaps) {
            val intervalTree = IntervalTree(collectedEmits)
            collectedEmits = intervalTree.removeOverlaps(collectedEmits) as List<PayloadEmit<T>>
        }

        return collectedEmits
    }

    /**
     * Returns true if the text contains one of the search terms; otherwise,
     * returns false.
     *
     * @param text Specified text.
     * @return true if the text contains one of the search terms. Else, returns
     * false.
     */
    fun containsMatch(text: CharSequence): Boolean {
        return firstMatch(text) != null
    }

    /**
     * Tokenizes the specified text by using a custom EmitHandler and returns the
     * emitted outputs.
     *
     * @param text        The character sequence to tokenize.
     * @param emitHandler The handler that will be used to parse the text.
     */
    fun parseText(text: CharSequence, emitHandler: PayloadEmitHandler<T>) {
        var currentState= getRootState()

        for (position in 0..<text.length) {
            var character: Char = text[position]

            if (trieConfig.isCaseInsensitive) {
                character = character.lowercaseChar()
            }

            currentState = getState(currentState, character)
            val payloads = currentState.emit()
            if (processEmits(text, position, payloads, emitHandler) && trieConfig.isStopOnHit) {
                return
            }
        }
    }

    /**
     * The first matching text sequence.
     *
     * @param text The text to search for keywords, must not be `null`.
     * @return `null` if no matches found.
     */
    fun firstMatch(text: CharSequence): PayloadEmit<T>? {
        checkNotNull(text)

        if (!trieConfig.isAllowOverlaps) {
            // Slow path. Needs to find all the matches to detect overlaps.
            val parseText = parseText(text)

            if ( !parseText.isEmpty()) {
                return parseText.iterator().next()
            }
        } else {
            // Fast path. Returns first match found.
            var currentState = getRootState()

            for (position in 0..<text.length) {
                var character: Char = text[position]

                if (trieConfig.isCaseInsensitive) {
                    character = character.lowercaseChar()
                }

                currentState = getState(currentState, character)
                val payloads = currentState.emit()

                if (!payloads.isEmpty()) {
                    for (payload in payloads) {
                        val emit: PayloadEmit<T> = PayloadEmit<T>(
                            position - payload.keyword.length+ 1, position,
                            payload.keyword, payload.data
                        )
                        if (trieConfig.isOnlyWholeWords) {
                            if (!isPartialMatch(text, emit)) {
                                return emit
                            }
                        } else {
                            return emit
                        }
                    }
                }
            }
        }

        return null
    }

    private fun isPartialMatch(searchText: CharSequence, emit: PayloadEmit<T>): Boolean {
        searchText[emit.start - 1].isAscii
        return (emit.start != 0 && searchText[emit.start - 1].isAlphabetic)
                || (emit.end + 1 != searchText.length && searchText[emit.end + 1].isAlphabetic)
//        return (emit.start != 0 && Char.isAlphabetic(searchText[emit.start - 1]))
//                || (emit.end + 1 != searchText.length && Char.isAlphabetic(searchText[emit.end + 1]))
    }

    private fun isPartialMatchWhiteSpaceSeparated(searchText: CharSequence, emit: PayloadEmit<T>): Boolean {
        val size = searchText.length
        return (emit.start != 0 && !searchText[emit.start - 1].isWhitespace())
                || ((emit.end + 1)!= size && !searchText[emit.end + 1].isWhitespace())
    }

    private fun getState(currentState: PayloadState<T>, character: Char): PayloadState<T> {
        var currentState: PayloadState<T> = currentState
        var newCurrentState = currentState.nextState(character)

        while (newCurrentState == null) {
            currentState = currentState.failure!!
            newCurrentState = currentState.nextState(character)
        }

        return newCurrentState
    }

    private fun constructFailureStates() {
        //val queue: Queue<PayloadState<T>> = ()
        val queue = mutableListOf<PayloadState<T>>()
        val startState = getRootState()

        // First, set the fail state of all depth 1 states to the root state
        for (depthOneState in startState.states) {
            depthOneState.failure = startState
            queue.add(depthOneState)
        }

        // Second, determine the fail state for all depth > 1 state
        while (!queue.isEmpty()) {
            val currentState: PayloadState<T> = queue.removeLast()

            for (transition in currentState.transitions) {
                val targetState = currentState.nextState(transition)!!
                queue.add(targetState)

                var traceFailureState = currentState.failure
                while (traceFailureState?.nextState(transition) == null) {
                    traceFailureState = traceFailureState!!.failure
                }

                val newFailureState = traceFailureState.nextState(transition)!!
                targetState.failure = newFailureState
                targetState.addEmit(newFailureState.emit())
            }
        }
    }

    private fun processEmits(
        text: CharSequence,
        position: Int,
        payloads: Collection<Payload<T>>,
        emitHandler: PayloadEmitHandler<T>
    ): Boolean {
        var emitted = false
        for (payload in payloads) {
            val payloadEmit = PayloadEmit(
                position - payload.keyword.length+ 1,
                position, payload.keyword, payload.data
            )
            if (!(trieConfig.isOnlyWholeWords && isPartialMatch(text, payloadEmit)) &&
                !(trieConfig.isOnlyWholeWordsWhiteSpaceSeparated && isPartialMatchWhiteSpaceSeparated(
                    text,
                    payloadEmit
                ))
            ) {
                emitted = emitHandler.emit(payloadEmit) || emitted
                if (emitted && trieConfig.isStopOnHit) {
                    break
                }
            }
        }

        return emitted
    }

    private val isCaseInsensitive: Boolean
        get() = trieConfig.isCaseInsensitive

    private fun getRootState(): PayloadState<T> {
        return this.rootState
    }

    /**
     * Builder class to create a PayloadTrie instance.
     *
     * @param <T> The type of the emitted payload.
    </T> */
    class PayloadTrieBuilder<T>() {
        private val trieConfig: TrieConfig = TrieConfig()

        private val trie: PayloadTrie<T> = PayloadTrie(trieConfig)

        /**
         * Configure the Trie to ignore case when searching for keywords in the text.
         * This must be called before calling addKeyword because the algorithm converts
         * keywords to lowercase as they are added, depending on this case sensitivity
         * setting.
         *
         * @return This builder.
         */
        fun ignoreCase(): PayloadTrieBuilder<T> {
            this.trieConfig.isCaseInsensitive = true
            return this
        }

        /**
         * Configure the Trie to ignore overlapping keywords.
         *
         * @return This builder.
         */
        fun ignoreOverlaps(): PayloadTrieBuilder<T> {
            this.trieConfig.isAllowOverlaps = false
            return this
        }

        /**
         * Adds a keyword to the [Trie]'s list of text search keywords.
         * No [Payload] is supplied.
         *
         * @param keyword The keyword to add to the list.
         * @return This builder.
         * @throws NullPointerException if the keyword is null.
         */
        fun addKeyword(keyword: String): PayloadTrieBuilder<T> {
            this.trie.addKeyword(keyword)
            return this
        }

        /**
         * Adds a keyword and a payload to the [Trie]'s list of text
         * search keywords.
         *
         * @param keyword The keyword to add to the list.
         * @param payload the payload to add
         * @return This builder.
         * @throws NullPointerException if the keyword is null.
         */
        fun addKeyword(keyword: String, payload: T?): PayloadTrieBuilder<T> {
            this.trie.addKeyword(keyword, payload)
            return this
        }

        /**
         * Adds a list of keywords and payloads to the [Trie]'s list of
         * text search keywords.
         *
         * @param keywords The keywords to add to the list.
         * @return This builder.
         */
        fun addKeywords(keywords: Collection<Payload<T>>): PayloadTrieBuilder<T> {
            for (payload in keywords) {
                this.trie.addKeyword(payload.keyword, payload.data)
            }
            return this
        }

        /**
         * Configure the Trie to match whole keywords in the text.
         *
         * @return This builder.
         */
        fun onlyWholeWords(): PayloadTrieBuilder<T> {
            this.trieConfig.isOnlyWholeWords = true
            return this
        }

        /**
         * Configure the Trie to match whole keywords that are separated by whitespace
         * in the text. For example, "this keyword thatkeyword" would only match the
         * first occurrence of "keyword".
         *
         * @return This builder.
         */
        fun onlyWholeWordsWhiteSpaceSeparated(): PayloadTrieBuilder<T> {
            this.trieConfig.isOnlyWholeWordsWhiteSpaceSeparated = true
            return this
        }

        /**
         * Configure the Trie to stop after the first keyword is found in the text.
         *
         * @return This builder.
         */
        fun stopOnHit(): PayloadTrieBuilder<T> {
            trie.trieConfig.isStopOnHit = true
            return this
        }

        /**
         * Configure the PayloadTrie based on the builder settings.
         *
         * @return The configured PayloadTrie.
         */
        fun build(): PayloadTrie<T> {
            this.trie.constructFailureStates()
            return this.trie
        }

//        /**
//         * @return This builder.
//         */
//        @Deprecated
//        @Deprecated("Use ignoreCase()")
//        fun caseInsensitive(): PayloadTrieBuilder<T> {
//            return ignoreCase()
//        }
//
//        /**
//         * @return This builder.
//         */
//        @Deprecated
//        @Deprecated("Use ignoreOverlaps()")
//        fun removeOverlaps(): PayloadTrieBuilder<T> {
//            return ignoreOverlaps()
//        }
    }

    companion object {
        /**
         * Provides a fluent interface for constructing Trie instances with payloads.
         * @param <T> The type of the emitted payload.
         *
         * @return The builder used to configure its Trie.
        </T> */
        fun <T> builder(): PayloadTrieBuilder<T> {
            return PayloadTrie.PayloadTrieBuilder()
        }
    }
}
